O(n^2)排序算法 3
- 冒泡排序
- 插入排序
- 选择排序
选择排序不稳定，相同元素可能会变化，因此这三种不选择选择排序。
代码中，把执行一个赋值语句的时间粗略地计为单位时间。冒泡排序需要 3 个赋值操作temp存储临时变量，而插入排序只需要 1 个 a[j]=a[j+1]移动数据。时间比值：1：7。
最优方法：插入排序。
O(nlogn) 排序算法 3
归并排序
方法：利用了分治思想，用递归代码来实现归并排序。先分，再合。
时间复杂度： T(n)=Cn+nlog2n。非常稳定，所有情况都是O(nlogn)。
- 空间复杂度：不是原地排序算法，每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时空间释放。 O(n)。
- 处理过程：是由下到上的，先处理子问题，然后再合并。
快速排序
方法：利用主元分区，每次分为左边小区，右边大区。直至区内只有一个元素之后，排序完成。
时间复杂度：分区每次右边都没有元素。就从 O(nlogn) 退化成了 O(n2)。
处理过程：是由上到下的，先分区，然后再处理子问题。
堆排序
10 亿个搜索关键词的日志文件，Top 10 最热门的搜索关键词
用户搜索的关键词，有很多可能都是重复的，散列表先记录次数。
用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出次数，若次数多>顶堆，则删除顶堆。遍历完成后得到top10。
然而10亿太大了。
哈希之后，将 10 亿条搜索关键词先通过哈希算法分到10个文件。在进行上述步骤，然后得到10x10个关键字。租后排序得到top10。
问题
10 个接口访问日志文件，每个日志文件大小约 300MB，日志都是按照时间戳从小到大排序的
将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后也是从小到大排序。
机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这10 个日志文件合并吗？
每次从各个文件中取一条数据，在内存中根据数据时间戳构建一个最小堆，然后每次把最小值给写入新文件，同时将最小值来自的那个文件再出来一个数据，加入到最小堆中。这个空间复杂度为常数，但没能很好利用1g内存，而且磁盘单个读取比较慢，所以考虑每次读取一批数据，没了再从磁盘中取，时间复杂度还是一样O(n)。
线性排序 3
桶排序（Bucket sort）
要求：
- 容易划分为m个桶，且天然有序
- 分布均匀，若分布不均匀全在一个桶里会退化为log（n/m log(n/m)) = log(n logn)
- 外部排序。数据大，内存有限，无法将数据全部加载到内存，存放于外部磁盘中。
10GB数据，如何按照订单金额排序？
扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 1…
将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内，第二个1001-2000，类推。每个桶按照范围命名。
- 理想状态均匀分布，则划分为100个100M文件。按文件编号，依次将文件放入内存快排，在写入同一个文件。
- 若部分文件很大，无法写入内存，继续划分，直到对所有文件都可读入内存为止，再依次快排。
计数排序（Counting sort）
要求：
- 数据量大，数据区间小
- 非负整数。若为不符合该条件，则转化即可。
如何根据年龄给 100 万用户排序？
年龄的范围最小 1 岁，最大不超过 120 岁；
遍历这 100 万用户，根据年龄将其划分到这 120 个桶里；
依次顺序遍历这 120 个桶中的元素。
高考查分系统，省内50万名考生，分数范围为900-0。
数据范围小，我们划分为901个桶，桶内为分数相同的学生。
此时不需要在排序，而是只需要依次输出到数组即可，只需一次扫描操作，时间复杂度O(n)。
ps. 若考生分数有小数点后一位，则需要所有分数乘10，转为整数，再放进9010个桶内。
基数排序（Radix sort）
要求：
- 数据可以分割出独立的“位”来比较，位之间有递进的关系（高位优先）
- 每一位的数据范围不能太大，要可以用线性排序算法来排序
10万个11位电话号码排序（等长）
- 规律：比较两个号码a、b，若前几位a已经大于b，则后面不用看。
- 方法：先按照最后一位排序，再按照倒数第二位，以此类推。最后按照第一位来排序。11排序之后，手机号码有序。
- 时间复杂度：按照每一位排序，数字只有0-10，可以使用桶排序，时间复杂度可以做到 O(n)。排序的数据有 k 位，时间为O(k*n)。k不大的时候，近似为O(n)。
排序牛津字典中的20 万个英文单词（非等长1-45）
- 解决非等长：把所有的单词补齐到相同长度，位数不够的可以在后面补“0”。根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响排序。
- 接着使用基数排序